package leetcode.editor.cn.q1_300.q100;

import java.util.*;

/**
 * @author qidi
 * @date 2022-01-17 09:58:27
 */
class Q0140_WordBreakIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        List<String> ans;
        LinkedList<String> cur;
        Map<Integer, List<String>> map;
        int maxLen;
        int minLen;


        public List<String> wordBreak(String s, List<String> wordDict) {
            ans = new ArrayList<>();
            cur = new LinkedList<>();
            map = new HashMap<>();

            maxLen = 0;
            minLen = s.length();

            for (String w : wordDict) {
                int len = w.length();
                maxLen = Math.max(maxLen, len);
                minLen = Math.min(minLen, len);
                map.putIfAbsent(len, new ArrayList<>());
                map.get(len).add(w);
            }

            process(s, 0);

            return ans;
        }

        private void process(String s, int i) {
            if (i == s.length()) {
                ans.add(String.join(" ", cur));
            }

            for (int j = i + minLen; j <= i + maxLen && j <= s.length(); j++) {
                String w = s.substring(i, j);
                int len = w.length();
                if (map.containsKey(len) && map.get(len).contains(w)) {
                    cur.add(w);
                    process(s, j);
                    cur.removeLast();
                }
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0140_WordBreakIi().new Solution();
        System.out.println(solution.wordBreak("catsanddog", Arrays.asList("cat", "cats", "and", "sand", "dog")));
        System.out.println(solution.wordBreak("catsandog", Arrays.asList("cat", "cats", "and", "sand", "dog")));
        System.out.println(solution.wordBreak("pineapplepenapple", Arrays.asList("apple", "pen", "applepen", "pine", "pineapple")));
//        System.out.println(
//                solution.wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
//                        Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa")));
    }
}